import java.util.Stack;

public class Sort {
    public static int Potion(int[] array,int start,int end){
        int key = array[start];
        while(start<end){
            while(start<end&&array[end]>=key){
                end--;
            }
            array[start] = array[end];
            while(start<end&&array[start]<=key){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = key;
        return start;
    }
    public void quickSort(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int porive = Potion(array,left,right);
        if(porive>left+1){
            stack.push(left);
            stack.push(porive-1);
        }
        if(porive<right-1){
            stack.push(porive+1);
            stack.push(right);
        }
        while(!stack.empty()){
            right = stack.pop();
            left = stack.pop();
            porive = Potion(array,left,right);
            if(porive>left+1){
                stack.push(left);
                stack.push(porive-1);
            }
            if(porive<right-1){
                stack.push(porive+1);
                stack.push(right);
            }
        }
    }
    public void insertSort(int[] array){
        int n = array.length;
        for (int i = 1; i <n ; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >=0 ; j--) {
                if(array[j]>tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    public void shell(int[] array,int gap){
        int n = array.length;
        for (int i = gap; i < n; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >=0 ; j-=gap) {
                if(array[j]>tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    public void shellSort(int[] array){
        int gap = array.length;
        while(gap>1){
            shell(array,gap);
            gap/=2;
        }
        shell(array,1);
    }

    public void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public void seclectSort(int[] array){
        int n = array.length;
        for (int i = 0; i < n; i++) {
            int minIndex = i;
            for (int j = i+1; j <n ; j++) {
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }
    public void seclectSort2(int[] array){
        int left = 0;
        int right = array.length-1;
        while(left<right){
            int minInedx = left;
            int maxIndex = left;
            for (int i = left+1; i < array.length; i++) {
                if(array[i]<array[minInedx]){
                    minInedx = i;
                }
                if(array[i]>array[maxIndex]){
                    maxIndex = i;
                }
            }
            swap(array,left,minInedx);
            //修正maxIndex的值
            if(left == maxIndex){
                maxIndex = minInedx;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }

    public void creatBigHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
            shiftDown(array,parent,array.length);
        }
    }
    public void shiftDown(int[] array,int parent,int len) {
        int child = 2 * parent + 1;
        while (child < len){
            if (child + 1 < len && array[child + 1] < array[child]) {
                child++;
            }
            if (array[child] > array[parent]) {
                swap(array, parent, child);
                parent = child;
                child = 2*parent+1;
            } else {
                break;
            }
        }
    }
    public void HeapSort(int[] array){
        creatBigHeap(array);//创建大根堆
        int end = array.length-1;
        while(end>=0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
}
